#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <stdlib.h>
#include <cstdio>
#include <cstdint>
#include <ctime>
#include <stack>
#include <string>
#include <queue>
#include <unistd.h>
#include <algorithm>

using namespace std;

//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    vector<vector<ListNode*>> test;
    //[c++优先队列(priority_queue)用法详解](https://blog.csdn.net/weixin_36888577/article/details/79937886)
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //声明小顶堆
        priority_queue<pair<int, ListNode*>, vector<pair<int, ListNode*>>, greater<pair<int, ListNode*>> > que;
        ListNode* root = NULL;
        ListNode* node;
        int flag = 0;
        //空数组检查
        // if (lists.empty()) return NULL;
        //堆先初始化
        for(vector<ListNode*>::iterator iter = lists.begin();iter != lists.end();iter++){
            if ((*iter)){
                que.push(pair<int, ListNode*>((*iter)->val, *iter));
            }
        }  
        //检查堆是否为空
        while (!que.empty()){
            pair<int, ListNode*> par = que.top();
            //弹出堆顶元素
            que.pop();
            if (!flag){
                root = new ListNode(par.first);
                node = root;
                flag = 1;
            }else{
                ListNode* newNode = new ListNode(par.first);
                node->next = newNode;
                node = newNode;
            }
            //取弹出元素的下一个，重新推入堆中
            if (par.second->next){
                par = pair<int, ListNode*>(par.second->next->val, par.second->next);
                que.push(par);
            }
        }
        return root;
    }
};

void delay(int ms)
{
    uint32_t curMs = clock();
    while(clock() < curMs + ms);
}

ListNode* createList(int num, uint32_t max)
{
    ListNode* head = NULL;
    ListNode* node = NULL;
    if (0 == num) return NULL;
    delay(10);
    srand(time(NULL) * 1000 + clock());
    head = new ListNode(rand()%max);
    node = head;
    for (int i = 0; i < num-1; i++){
        node->next = new ListNode(rand()%max);
        node = node->next;
    }
    return head;
}

void printList(ListNode* node)
{
    int cnt = 0;
    cout << "list node: ";
    while(node){
        cout << node->val << " ";
        node = node->next;
    }
    cout << endl;
}
 
int main()
{
    Solution su;
    su.test.push_back({createList(10, 10), createList(10, 10), createList(10, 10), createList(10, 10), createList(10, 10)});
    su.test.push_back({createList(10, 10), createList(10, 10), createList(10, 10), createList(10, 10), createList(10, 10)});
    su.test.push_back({createList(10, 10), createList(10, 10)});
    su.test.push_back({createList(10, 10), createList(10, 10)});

    for (int i = 0; i < su.test.size(); i++){
        ListNode*  result = su.mergeKLists(su.test[i]);
        // printf("result %d is %p\r\n", i, result);
        printList(result);
    }

    return 0;
}